public class JobSchedulingProblem {
    /**
     * 作业调度问题
     */
    private int[] jobs;
    private int[] bestSequence;
    private int bestCompletionTime;

    public JobSchedulingProblem(int[] jobs) {
        this.jobs = jobs;
        this.bestSequence = new int[jobs.length];
        this.bestCompletionTime = Integer.MAX_VALUE;
    }

    public void solve() {
        int[] sequence = new int[jobs.length];
        boolean[] assigned = new boolean[jobs.length];
        int completionTime = 0;
        backtrack(sequence, assigned, completionTime, 0);
    }

    private void backtrack(int[] sequence, boolean[] assigned, int completionTime, int level) {
        if (level == sequence.length) {
            if (completionTime < bestCompletionTime) {
                System.arraycopy(sequence, 0, bestSequence, 0, sequence.length);
                bestCompletionTime = completionTime;
            }
            return;
        }

        for (int i = 0; i < sequence.length; i++) {
            if (!assigned[i]) {
                sequence[level] = jobs[i];
                assigned[i] = true;
                backtrack(sequence, assigned, completionTime + jobs[i], level + 1);
                assigned[i] = false;
            }
        }
    }

    public int[] getBestSequence() {
        return bestSequence;
    }

    public int getBestCompletionTime() {
        return bestCompletionTime;
    }

    public static void main(String[] args) {
        int[] jobs = {2,1,3,1,2,3};

        JobSchedulingProblem jsp = new JobSchedulingProblem(jobs);
        jsp.solve();
        int[] bestSequence = jsp.getBestSequence();
        int bestCompletionTime = jsp.getBestCompletionTime();

        System.out.println("Best Sequence: ");
        for (int job : bestSequence) {
            System.out.print(job + " ");
        }
        System.out.println("\nBest Completion Time: " + bestCompletionTime);
    }

}
